﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

class SOl25
{
    public ListNode reverse2(ListNode head, ListNode nail)//迭代方法
    {

        ListNode result = new ListNode();
        ListNode next = new ListNode();
        while (head != nail)
        {


            next = head.next;
            head.next = result.next;

            result.next = head;
            head = next;

        }

        return result.next;
    }

    public ListNode ReverseKGroup(ListNode head,int interval)//递归方法
    {

        ListNode pre = head;
        for (int i = 0; i < interval; i++) {


            //3,正确
            if (head == null)//小于K，直接原样返回
            {
                return pre;
            }
            head = head.next;

            //1,错误
            //head = head.next;
            //if (head == null)
            //{
            //    return pre;
            //}

            //2,错误
            //head = head.next;
            //if (head.next == null)
            //{
            //    return pre;
            //}
        }

        ListNode newHead = reverse2(pre, head);//先反转一部分，返回的newHead是head,尾巴是pre
        pre.next= ReverseKGroup(head, interval);//反转剩下的，结果怎么接过来？
        return newHead;



    }

}
class Program25
{
    static void Main25(string[] args)
    {

        //先创建一个链表

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        for (int i = 1; i < 16; i++)//这个叫做尾插法
        {
            ListNode newNode = new ListNode(i);


            cur.next = newNode;
            cur = newNode;
        }

        //while (head != null)
        //{
        //    Console.WriteLine(head.val);
        //    head = head.next;
        //}

        SOl25 sol = new SOl25();
        int k = 2;
        ListNode res = sol.ReverseKGroup(head.next,k);
        while (res != null)
        {
            Console.WriteLine(res.val);
            res = res.next;
        }
        Console.ReadKey();
    }



}
